package xiaomin.demo.algorithm;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
/*
给定 多个 可能 重叠 的 区间， 找出 重叠 区间 的 个数。 区间 定义 如下：
 class Interval{
 int start; //起点
 int end; //止 点
 Interval( int a, int b)
 { start= a; end= b; }
 }

陈东锋. 进军硅谷:程序员面试揭秘 (技术移民参考手册) (p. 67). 电子工业出版社. Kindle 版本.

思路：
1.构建一个Point类型数组,包含一个属性,start,end(类似括号的左括号右括号),对区间进行排序
2.按照类似括号配对的方式,对列表进行遍历,记录左括号重叠的最大数,则为重叠区间的个数
 */
public class Lesson06 {
    static class Interval{
        int start;
        int end;
        Interval(int a,int b){
            start=a;
            end=b;
        }
    }
    public static void run(){
        //构建4个区间
        Interval[] intervals=new Interval[4];
        intervals[0]=new Interval(1,5);
        intervals[1]=new Interval(5,10);
        intervals[2]=new Interval(20,30);
        intervals[3]=new Interval(10,15);

        //把4个区间打平成8个点
        List<Point> points=new ArrayList<Point>();
        for(int i=0;i<intervals.length;i++){
            //左
            points.add(new Point(intervals[i].start,0));
            //右
            points.add(new Point(intervals[i].end,1));
        }

        //排序
        Collections.sort(points);

        int count=0,result=1;//count用于记录遍历过程中的重叠数量，遍历结束后会变成0，max记录最大值
        for(Point p:points){

            System.out.println(p);
            //如果有一个左括号
            if(p.type==0){
                if(count>0) {//如果前面已经打开了，则重叠数加一
                    result ++;
                }
                count++;//打开的区间加一
                System.out.println(count);

            }
            else {
                count--;
                System.out.println(count);
            }
        }

        System.out.println(result);

    }

    static class Point implements Comparable<Point>{
        int value;
        int type;//0:start;1:end

        Point(int v,int t){
            value=v;
            type=t;
        }


        public int compareTo(Point o) {
            if(this.value>o.value){
                return 1;
            }
            else if(this.value<o.value){
                return -1;
            }
            else {
                //类型不同 star end值相同 则 end更大，在后面
                // 1        5      5      10
                // start   start  end     end
                if(o.type!=this.type){
                    System.out.println("相等"+this.value);
                    if(this.type==1) return 1;
                    else return -1;
                }
                else {
                    return 0;
                }

            }
        }

        @Override
        public String toString() {
            return "Point{" +
                    "value=" + value +
                    ", type=" + type +
                    '}';
        }
    }
}
